package tree.easy;

import tree.TreeNode;

public class isValidBST {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5, new TreeNode(3,new TreeNode(1), new TreeNode(6)), new TreeNode(8, new TreeNode(7), new TreeNode(9)));
        System.out.println(new isValidBST().myCode(root));
    }

    public boolean myCode(TreeNode root) {
        return test(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }


    /**
     * 需验证根节点及其子树是否符合二叉搜索树规则
     * 当检验左子树时，根节点是最大值，当检验右子树时，根节点是最小值
     * @param root
     * @param lower
     * @param upper
     * @return
     */
    public boolean test(TreeNode root, long lower, long upper) {
        if (null == root) {
            return true;
        }
        if (root.val <= lower || root.val >= upper) {
            return false;
        }
        return test(root.left, lower, root.val) && test(root.right, root.val, upper);
    }
}
